import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class HuffmanTreeDemo {
        // 生成哈夫曼编码（递归遍历树）
        public static void generateCode(HuffmanNode node, String code, Map<String, String> codeMap) {
            if (node == null) {
                return;
            }
            // 叶子结点：记录编码
            if (node.left == null && node.right == null) {
                node.code = code;
                codeMap.put(node.word, code);
                return;
            }
            // 左子树：编码加"0"
            generateCode(node.left, code + "0", codeMap);
            // 右子树：编码加"1"
            generateCode(node.right, code + "1", codeMap);
        }

        // 计算WPL（带权路径长度）
        public static int calculateWPL(HuffmanNode node, int depth) {
            if (node == null) {
                return 0;
            }
            // 叶子结点：权重×深度
            if (node.left == null && node.right == null) {
                return node.weight * depth;
            }
            // 非叶子结点：递归计算左右子树的WPL之和
            return calculateWPL(node.left, depth + 1) + calculateWPL(node.right, depth + 1);
        }

        public static void main(String[] args) {
            // 表7.4的单词及频度
            String[] words = {"The", "of", "a", "to", "and", "in", "that", "he", "is", "at", "on", "for", "His", "are", "be"};
            int[] weights = {1192, 677, 541, 518, 462, 450, 242, 195, 190, 181, 174, 157, 138, 124, 123};

            // 1. 初始化优先队列（最小堆）
            PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
            for (int i = 0; i < words.length; i++) {
                pq.offer(new HuffmanNode(words[i], weights[i]));
            }

            // 2. 构造哈夫曼树
            while (pq.size() > 1) {
                // 取出权重最小的两个结点
                HuffmanNode left = pq.poll();
                HuffmanNode right = pq.poll();
                // 合并为新结点（权重为两者之和）
                HuffmanNode parent = new HuffmanNode(left.weight + right.weight, left, right);
                pq.offer(parent);
            }
            HuffmanNode root = pq.poll(); // 哈夫曼树的根结点

            // 3. 生成哈夫曼编码
            Map<String, String> codeMap = new HashMap<>();
            generateCode(root, "", codeMap);

            // 4. 输出结果
            System.out.println("哈夫曼编码：");
            for (String word : words) {
                System.out.println(word + " : " + codeMap.get(word));
            }

            // 5. 计算并输出WPL
            int wpl = calculateWPL(root, 0);
            System.out.println("\nWPL（带权路径长度）：" + wpl);
        }
    }

